{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "matrix([[-0.41027118, -3.38196001],\n",
       "        [ 3.62454065,  2.75254609]])"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from numpy import *\n",
    "\n",
    "\n",
    "def loadDataSet(fileName):  #general function to parse tab -delimited floats\n",
    "    dataMat = []  #assume last column is target value\n",
    "    fr = open(fileName)\n",
    "    for line in fr.readlines():\n",
    "        curLine = line.strip().split('\\t')\n",
    "        for i in range(len(curLine)):\n",
    "            curLine[i] = float(curLine[i])\n",
    "        dataMat.append(curLine)\n",
    "    return dataMat\n",
    "\n",
    "\n",
    "def distEclud(vecA, vecB):\n",
    "    return sqrt(sum(power(vecA - vecB, 2)))\n",
    "\n",
    "\n",
    "def randCent(dataSet, k):\n",
    "    n = shape(dataSet)[1]\n",
    "    centroids = mat(zeros((k, n)))\n",
    "    for j in range(n):\n",
    "        minJ = min(dataSet[:, j])\n",
    "        rangeJ = float(max(dataSet[:, j]) - minJ)\n",
    "        centroids[:, j] = mat(minJ + rangeJ * random.rand(k, 1))\n",
    "    return centroids\n",
    "\n",
    "\n",
    "datMat = mat(loadDataSet('testSet.txt'))\n",
    "randCent(datMat, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-5.379713, 4.838138, -4.232586, 5.1904)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "datMat[:, 0].min(), datMat[:, 0].max(), datMat[:, 1].min(), datMat[:, 1].max()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5.184632816681332"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "distEclud(datMat[0], datMat[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-3.09607558 -4.16880927]\n",
      " [ 3.80978619 -2.45850965]\n",
      " [ 1.58581126  4.35758987]\n",
      " [-4.49084032 -3.74599714]]\n",
      "[[-2.5660635  -3.0692904 ]\n",
      " [ 2.8692781  -2.54779119]\n",
      " [ 0.14460654  3.09399208]\n",
      " [-4.01947533 -2.16142433]]\n",
      "[[-2.38267313 -3.20383625]\n",
      " [ 2.8692781  -2.54779119]\n",
      " [ 0.14460654  3.09399208]\n",
      " [-3.91663957 -2.21423614]]\n",
      "[[-2.32402057 -3.35442629]\n",
      " [ 2.8692781  -2.54779119]\n",
      " [ 0.14460654  3.09399208]\n",
      " [-3.84174633 -2.20993413]]\n",
      "[[-2.28373583 -3.578145  ]\n",
      " [ 2.8692781  -2.54779119]\n",
      " [ 0.14460654  3.09399208]\n",
      " [-3.76199525 -2.19757038]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(matrix([[-2.28373583, -3.578145  ],\n",
       "         [ 2.8692781 , -2.54779119],\n",
       "         [ 0.14460654,  3.09399208],\n",
       "         [-3.76199525, -2.19757038]]),\n",
       " matrix([[2.00000000e+00, 3.71216595e+00],\n",
       "         [2.00000000e+00, 1.30568336e+01],\n",
       "         [1.00000000e+00, 5.82592950e+00],\n",
       "         [3.00000000e+00, 3.97314928e+00],\n",
       "         [2.00000000e+00, 7.14381631e-01],\n",
       "         [3.00000000e+00, 1.39444593e+01],\n",
       "         [1.00000000e+00, 6.41909733e+00],\n",
       "         [3.00000000e+00, 2.99424571e-01],\n",
       "         [2.00000000e+00, 8.61879660e+00],\n",
       "         [2.00000000e+00, 1.09066425e+01],\n",
       "         [1.00000000e+00, 2.19619091e+00],\n",
       "         [0.00000000e+00, 4.82351606e-01],\n",
       "         [2.00000000e+00, 1.65245813e+01],\n",
       "         [2.00000000e+00, 5.16625612e+00],\n",
       "         [1.00000000e+00, 8.96547453e+00],\n",
       "         [0.00000000e+00, 3.72592046e+00],\n",
       "         [2.00000000e+00, 9.53061512e+00],\n",
       "         [2.00000000e+00, 9.35852077e-01],\n",
       "         [1.00000000e+00, 6.60448582e-01],\n",
       "         [3.00000000e+00, 3.27940374e-01],\n",
       "         [2.00000000e+00, 4.85206695e+00],\n",
       "         [2.00000000e+00, 4.01989752e+00],\n",
       "         [1.00000000e+00, 8.73151788e-01],\n",
       "         [3.00000000e+00, 4.65847182e-01],\n",
       "         [2.00000000e+00, 3.28749635e+00],\n",
       "         [2.00000000e+00, 4.10573603e+00],\n",
       "         [1.00000000e+00, 3.19809293e-01],\n",
       "         [3.00000000e+00, 1.07923474e+00],\n",
       "         [2.00000000e+00, 4.55149213e+00],\n",
       "         [3.00000000e+00, 1.00692908e+01],\n",
       "         [1.00000000e+00, 5.90189962e+00],\n",
       "         [3.00000000e+00, 1.17027044e-02],\n",
       "         [2.00000000e+00, 3.74495715e+00],\n",
       "         [2.00000000e+00, 1.28419347e+01],\n",
       "         [1.00000000e+00, 5.23761436e+00],\n",
       "         [0.00000000e+00, 9.38589987e-02],\n",
       "         [2.00000000e+00, 7.43795332e+00],\n",
       "         [2.00000000e+00, 1.71511388e+00],\n",
       "         [1.00000000e+00, 1.33419358e-02],\n",
       "         [3.00000000e+00, 1.12141075e+00],\n",
       "         [2.00000000e+00, 4.43796041e+00],\n",
       "         [2.00000000e+00, 8.17220007e+00],\n",
       "         [1.00000000e+00, 6.53530137e-01],\n",
       "         [0.00000000e+00, 4.54620302e-01],\n",
       "         [2.00000000e+00, 4.78131726e+00],\n",
       "         [2.00000000e+00, 1.17930182e+01],\n",
       "         [1.00000000e+00, 1.65575057e+00],\n",
       "         [3.00000000e+00, 5.50468472e-02],\n",
       "         [2.00000000e+00, 1.16419887e+01],\n",
       "         [2.00000000e+00, 4.85549458e+00],\n",
       "         [1.00000000e+00, 7.40867458e-01],\n",
       "         [3.00000000e+00, 3.34514388e+00],\n",
       "         [2.00000000e+00, 1.74732106e+01],\n",
       "         [2.00000000e+00, 2.43855347e+01],\n",
       "         [1.00000000e+00, 5.68381974e-01],\n",
       "         [3.00000000e+00, 6.70409056e-01],\n",
       "         [2.00000000e+00, 6.79495551e+00],\n",
       "         [2.00000000e+00, 7.27053674e+00],\n",
       "         [1.00000000e+00, 1.40486487e+00],\n",
       "         [0.00000000e+00, 7.87596659e-01],\n",
       "         [2.00000000e+00, 7.92623473e+00],\n",
       "         [2.00000000e+00, 7.37254989e+00],\n",
       "         [1.00000000e+00, 2.34578348e+00],\n",
       "         [3.00000000e+00, 1.46544701e+00],\n",
       "         [2.00000000e+00, 1.09560377e+01],\n",
       "         [2.00000000e+00, 3.33219934e+00],\n",
       "         [1.00000000e+00, 3.46660028e-01],\n",
       "         [0.00000000e+00, 3.60625880e-01],\n",
       "         [2.00000000e+00, 4.74212838e+00],\n",
       "         [2.00000000e+00, 3.37383999e+00],\n",
       "         [1.00000000e+00, 1.17633004e+00],\n",
       "         [3.00000000e+00, 7.01756432e-01],\n",
       "         [1.00000000e+00, 1.52624993e+01],\n",
       "         [2.00000000e+00, 5.19142354e+00],\n",
       "         [1.00000000e+00, 3.23883263e+00],\n",
       "         [3.00000000e+00, 9.40775795e-01],\n",
       "         [2.00000000e+00, 7.50740752e+00],\n",
       "         [2.00000000e+00, 9.74629227e+00],\n",
       "         [1.00000000e+00, 3.20539263e+00],\n",
       "         [3.00000000e+00, 1.81683578e+00]]))"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):\n",
    "    m = shape(dataSet)[0]\n",
    "    clusterAssment = mat(zeros((m, 2)))  #create mat to assign data points\n",
    "    #to a centroid, also holds SE of each point\n",
    "    centroids = createCent(dataSet, k)\n",
    "    clusterChanged = True\n",
    "    while clusterChanged:\n",
    "        clusterChanged = False\n",
    "        for i in range(m):\n",
    "            minDist = inf\n",
    "            minIndex = -1\n",
    "            for j in range(k):\n",
    "                distJI = distMeas(centroids[j, :], dataSet[i, :])\n",
    "                if distJI < minDist:\n",
    "                    minDist = distJI\n",
    "                    minIndex = j\n",
    "            if clusterAssment[i, 0] != minIndex: clusterChanged = True\n",
    "            clusterAssment[i, :] = minIndex, minDist**2\n",
    "        print(centroids)\n",
    "        for cent in range(k):  #recalculate centroids\n",
    "            ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A == cent)\n",
    "                                 [0]]  #get all the point in this cluster\n",
    "            centroids[cent, :] = mean(ptsInClust,\n",
    "                                      axis=0)  #assign centroid to mean\n",
    "    return centroids, clusterAssment\n",
    "\n",
    "\n",
    "kMeans(datMat, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 2.80217871  4.4455403 ]\n",
      " [ 1.89196769 -1.81039396]]\n",
      "[[ 0.34421986  3.07632743]\n",
      " [-0.48895795 -2.54604695]]\n",
      "[[ 0.08249337  2.94802785]\n",
      " [-0.2897198  -2.83942545]]\n",
      "sseSplit, and notSplit:  792.9168565373268 0.0\n",
      "the bestCentToSplit is:  0\n",
      "the len of bestClustAss is:  80\n",
      "[[3.74843532 3.29378414]\n",
      " [0.1190672  1.90485586]]\n",
      "[[ 2.71358074  3.11839563]\n",
      " [-2.29801424  2.79388557]]\n",
      "[[ 2.6265299   3.10868015]\n",
      " [-2.46154315  2.78737555]]\n",
      "sseSplit, and notSplit:  66.36683512000786 466.63278133614426\n",
      "[[-3.00689692 -0.81281695]\n",
      " [ 0.56446681 -1.4708354 ]]\n",
      "[[-3.53973889 -2.89384326]\n",
      " [ 2.65077367 -2.79019029]]\n",
      "sseSplit, and notSplit:  84.25921395268443 326.2840752011824\n",
      "the bestCentToSplit is:  1\n",
      "the len of bestClustAss is:  40\n",
      "[[ 3.91126049  4.22239662]\n",
      " [-2.54451044  3.29644494]]\n",
      "[[ 2.6265299   3.10868015]\n",
      " [-2.46154315  2.78737555]]\n",
      "sseSplit, and notSplit:  66.36683512000786 84.25921395268443\n",
      "[[-4.08032343 -2.2534253 ]\n",
      " [-3.2328623  -2.44447403]]\n",
      "[[-4.332724   -2.90944687]\n",
      " [-2.96302245 -2.88249518]]\n",
      "[[-4.277741  -2.94771  ]\n",
      " [-2.875537  -2.8453632]]\n",
      "sseSplit, and notSplit:  12.740153227591598 388.4400525969194\n",
      "[[ 0.10208819 -2.79539551]\n",
      " [ 0.63143375 -3.67383889]]\n",
      "[[ 1.44715    -1.1927505 ]\n",
      " [ 2.77747089 -2.95834184]]\n",
      "[[ 1.11497133 -1.89590667]\n",
      " [ 2.90674072 -2.93923756]]\n",
      "[[ 0.7784112  -2.7349974 ]\n",
      " [ 3.23588694 -2.80743806]]\n",
      "[[ 0.713266   -2.9890552 ]\n",
      " [ 3.25624481 -2.728045  ]]\n",
      "sseSplit, and notSplit:  37.261243813535245 348.38731175812995\n",
      "the bestCentToSplit is:  0\n",
      "the len of bestClustAss is:  40\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(matrix([[ 2.6265299 ,  3.10868015],\n",
       "         [-3.53973889, -2.89384326],\n",
       "         [ 2.65077367, -2.79019029],\n",
       "         [-2.46154315,  2.78737555]]),\n",
       " matrix([[ 0.        ,  2.3201915 ],\n",
       "         [ 3.        ,  1.39004893],\n",
       "         [ 2.        ,  7.46974076],\n",
       "         [ 1.        ,  3.60477283],\n",
       "         [ 0.        ,  2.7696782 ],\n",
       "         [ 3.        ,  2.80101213],\n",
       "         [ 2.        ,  5.10287596],\n",
       "         [ 1.        ,  1.37029303],\n",
       "         [ 0.        ,  2.29348924],\n",
       "         [ 3.        ,  0.64596748],\n",
       "         [ 2.        ,  1.72819697],\n",
       "         [ 1.        ,  0.60909593],\n",
       "         [ 0.        ,  2.51695402],\n",
       "         [ 3.        ,  0.13871642],\n",
       "         [ 2.        ,  9.12853034],\n",
       "         [ 2.        , 10.63785781],\n",
       "         [ 0.        ,  2.39726914],\n",
       "         [ 3.        ,  3.1024236 ],\n",
       "         [ 2.        ,  0.40704464],\n",
       "         [ 1.        ,  0.49023594],\n",
       "         [ 0.        ,  0.13870613],\n",
       "         [ 3.        ,  0.510241  ],\n",
       "         [ 2.        ,  0.9939764 ],\n",
       "         [ 1.        ,  0.03195031],\n",
       "         [ 0.        ,  1.31601105],\n",
       "         [ 3.        ,  0.90820377],\n",
       "         [ 2.        ,  0.54477501],\n",
       "         [ 1.        ,  0.31668166],\n",
       "         [ 0.        ,  0.21378662],\n",
       "         [ 3.        ,  4.05632356],\n",
       "         [ 2.        ,  4.44962474],\n",
       "         [ 1.        ,  0.41852436],\n",
       "         [ 0.        ,  0.47614274],\n",
       "         [ 3.        ,  1.5441411 ],\n",
       "         [ 2.        ,  6.83764117],\n",
       "         [ 1.        ,  1.28690535],\n",
       "         [ 0.        ,  4.87745774],\n",
       "         [ 3.        ,  3.12703929],\n",
       "         [ 2.        ,  0.05182929],\n",
       "         [ 1.        ,  0.21846598],\n",
       "         [ 0.        ,  0.8849557 ],\n",
       "         [ 3.        ,  0.0798871 ],\n",
       "         [ 2.        ,  0.66874131],\n",
       "         [ 1.        ,  3.80369324],\n",
       "         [ 0.        ,  0.09325235],\n",
       "         [ 3.        ,  0.91370546],\n",
       "         [ 2.        ,  1.24487442],\n",
       "         [ 1.        ,  0.26256416],\n",
       "         [ 0.        ,  0.94698784],\n",
       "         [ 3.        ,  2.63836399],\n",
       "         [ 2.        ,  0.31170066],\n",
       "         [ 1.        ,  1.70528559],\n",
       "         [ 0.        ,  5.46768776],\n",
       "         [ 3.        ,  5.73153563],\n",
       "         [ 2.        ,  0.22210601],\n",
       "         [ 1.        ,  0.22758842],\n",
       "         [ 0.        ,  1.32864695],\n",
       "         [ 3.        ,  0.02380325],\n",
       "         [ 2.        ,  0.76751052],\n",
       "         [ 1.        ,  0.59634253],\n",
       "         [ 0.        ,  0.45550286],\n",
       "         [ 3.        ,  0.01962128],\n",
       "         [ 2.        ,  2.04544706],\n",
       "         [ 1.        ,  1.72614177],\n",
       "         [ 0.        ,  1.2636401 ],\n",
       "         [ 3.        ,  1.33108375],\n",
       "         [ 2.        ,  0.19026129],\n",
       "         [ 1.        ,  0.83327924],\n",
       "         [ 0.        ,  0.09525163],\n",
       "         [ 3.        ,  0.62512976],\n",
       "         [ 2.        ,  0.83358364],\n",
       "         [ 1.        ,  1.62463639],\n",
       "         [ 0.        ,  6.39227291],\n",
       "         [ 3.        ,  0.20120037],\n",
       "         [ 2.        ,  4.12455116],\n",
       "         [ 1.        ,  1.11099937],\n",
       "         [ 0.        ,  0.07060147],\n",
       "         [ 3.        ,  0.2599013 ],\n",
       "         [ 2.        ,  4.39510824],\n",
       "         [ 1.        ,  1.86578044]]))"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def biKmeans(dataSet, k, distMeas=distEclud):\n",
    "    m = shape(dataSet)[0]\n",
    "    clusterAssment = mat(zeros((m, 2)))\n",
    "    centroid0 = mean(dataSet, axis=0).tolist()[0]\n",
    "    centList = [centroid0]  #create a list with one centroid\n",
    "    for j in range(m):  #calc initial Error\n",
    "        clusterAssment[j, 1] = distMeas(mat(centroid0), dataSet[j, :])**2\n",
    "    while (len(centList) < k):\n",
    "        lowestSSE = inf\n",
    "        for i in range(len(centList)):\n",
    "            ptsInCurrCluster = dataSet[nonzero(\n",
    "                clusterAssment[:, 0].A ==\n",
    "                i)[0], :]  #get the data points currently in cluster i\n",
    "            centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)\n",
    "            sseSplit = sum(\n",
    "                splitClustAss[:, 1])  #compare the SSE to the currrent minimum\n",
    "            sseNotSplit = sum(\n",
    "                clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1])\n",
    "            print(\"sseSplit, and notSplit: \", sseSplit, sseNotSplit)\n",
    "            if (sseSplit + sseNotSplit) < lowestSSE:\n",
    "                bestCentToSplit = i\n",
    "                bestNewCents = centroidMat\n",
    "                bestClustAss = splitClustAss.copy()\n",
    "                lowestSSE = sseSplit + sseNotSplit\n",
    "        bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0],\n",
    "                     0] = len(centList)  #change 1 to 3,4, or whatever\n",
    "        bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0],\n",
    "                     0] = bestCentToSplit\n",
    "        print('the bestCentToSplit is: ', bestCentToSplit)\n",
    "        print('the len of bestClustAss is: ', len(bestClustAss))\n",
    "        centList[bestCentToSplit] = bestNewCents[0, :].tolist()[\n",
    "            0]  #replace a centroid with two best centroids\n",
    "        centList.append(bestNewCents[1, :].tolist()[0])\n",
    "        clusterAssment[nonzero(\n",
    "            clusterAssment[:, 0].A == bestCentToSplit\n",
    "        )[0], :] = bestClustAss  #reassign new clusters, and SSE\n",
    "    return mat(centList), clusterAssment\n",
    "\n",
    "\n",
    "biKmeans(datMat, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[ 0.38994031  4.11754519]\n",
      " [-4.88010218 -3.50275644]]\n",
      "[[ 0.71260382  1.97554384]\n",
      " [-1.46397493 -3.14776987]]\n",
      "[[ 0.49695427  2.46978598]\n",
      " [-0.8757714  -3.05132209]]\n",
      "[[ 0.30731902  2.68529874]\n",
      " [-0.58118311 -3.00334459]]\n",
      "[[ 0.18713124  2.8560699 ]\n",
      " [-0.40926764 -2.89114795]]\n",
      "[[ 0.08249337  2.94802785]\n",
      " [-0.2897198  -2.83942545]]\n"
     ]
    },
    {
     "ename": "IndexError",
     "evalue": "too many indices for array: array is 2-dimensional, but 3 were indexed",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-17-6512ce3c5091>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     59\u001b[0m \u001b[0mN\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     60\u001b[0m \u001b[0mdistance\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdistEclud\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 61\u001b[0;31m \u001b[0mbiKmeans\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-17-6512ce3c5091>\u001b[0m in \u001b[0;36mbiKmeans\u001b[0;34m(x, k)\u001b[0m\n\u001b[1;32m     45\u001b[0m         \u001b[0;31m#被分为第二类的,设置为新的中心点\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     46\u001b[0m         \u001b[0;31m#被分为第一类的,代替原来被拆分的中心点\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 47\u001b[0;31m         \u001b[0mmin_pred_ki\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mmin_pred_ki\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcents\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     48\u001b[0m         \u001b[0mmin_pred_ki\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mmin_pred_ki\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmin_ki\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     49\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mIndexError\u001b[0m: too many indices for array: array is 2-dimensional, but 3 were indexed"
     ]
    }
   ],
   "source": [
    "def biKmeans(x, k):\n",
    "    #第一列是结果,第二列是距离\n",
    "    pred = zeros((N, 2))\n",
    "\n",
    "    #所有x的均值\n",
    "    mean_x = mean(x, axis=0).tolist()[0]\n",
    "\n",
    "    #中心点,初始化为1个,就是所有x的中心点\n",
    "    cents = [mean_x]\n",
    "\n",
    "    #计算所有点和这个中心点的距离,初始化pred\n",
    "    for i in range(N):\n",
    "        pred[i, 1] = distance(mean_x, x[i])**2\n",
    "\n",
    "    #只要不是每个点1个中心,循环就不停止\n",
    "    while (len(cents) < k):\n",
    "\n",
    "        min_d = inf\n",
    "\n",
    "        #遍历所有中心点,第一次的时候只有1个中心点\n",
    "        for ki in range(len(cents)):\n",
    "\n",
    "            #取属于这个中心点的x,第一次的时候是所有x\n",
    "            x_ki = x[pred[:, 0] == ki]\n",
    "\n",
    "            #调用k均值分为两类\n",
    "            #cents_ki=2个新的中心点\n",
    "            #pred_ki 第一列是分类,第二列是距离\n",
    "            cents_ki, pred_ki = kMeans(x_ki, 2)\n",
    "\n",
    "            #2分类后的距离求和,不论是分到哪一类的\n",
    "            distance_ki = sum(pred_ki[:, 1])\n",
    "\n",
    "            #不属于这个中心点的x,距离求和,第一次应该是0\n",
    "            distance_not_ki = sum(pred[pred[:, 0] != ki, 1])\n",
    "\n",
    "            #尝试把1个中心点,拆分为2个中心点,并且求哪一个中心点拆分后的总体距离是最小的\n",
    "            if (distance_ki + distance_not_ki) < min_d:\n",
    "                min_ki = ki\n",
    "                min_cents_ki = cents_ki\n",
    "                min_pred_ki = pred_ki.copy()\n",
    "                min_d = distance_ki + distance_not_ki\n",
    "\n",
    "        #第一列是分类,第二列是距离\n",
    "        #被分为第二类的,设置为新的中心点\n",
    "        #被分为第一类的,代替原来被拆分的中心点\n",
    "        min_pred_ki[min_pred_ki[:, 0] == 1, 0] = len(cents)\n",
    "        min_pred_ki[min_pred_ki[:, 0] == 0, 0] = min_ki\n",
    "\n",
    "        #min_cents_ki=2个新的中心点\n",
    "        cents[min_ki] = min_cents_ki[0].tolist()[0]\n",
    "        cents.append(min_cents_ki[1].tolist()[0])\n",
    "        pred[pred[:, 0] == min_ki] = min_pred_ki\n",
    "\n",
    "    return mat(cents), pred\n",
    "\n",
    "\n",
    "x = datMat\n",
    "N = len(x)\n",
    "distance = distEclud\n",
    "biKmeans(x, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "http://where.yahooapis.com/geocode?flags=J&appid=aaa0VN6k&location=l+VA+Center+Augusta%2C+ME\n"
     ]
    },
    {
     "ename": "URLError",
     "evalue": "<urlopen error [Errno -2] Name or service not known>",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mgaierror\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/urllib/request.py\u001b[0m in \u001b[0;36mdo_open\u001b[0;34m(self, http_class, req, **http_conn_args)\u001b[0m\n\u001b[1;32m   1317\u001b[0m                 h.request(req.get_method(), req.selector, req.data, headers,\n\u001b[0;32m-> 1318\u001b[0;31m                           encode_chunked=req.has_header('Transfer-encoding'))\n\u001b[0m\u001b[1;32m   1319\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mOSError\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0merr\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# timeout error\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/http/client.py\u001b[0m in \u001b[0;36mrequest\u001b[0;34m(self, method, url, body, headers, encode_chunked)\u001b[0m\n\u001b[1;32m   1261\u001b[0m         \u001b[0;34m\"\"\"Send a complete request to the server.\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1262\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_send_request\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmethod\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0murl\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbody\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mheaders\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mencode_chunked\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1263\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/http/client.py\u001b[0m in \u001b[0;36m_send_request\u001b[0;34m(self, method, url, body, headers, encode_chunked)\u001b[0m\n\u001b[1;32m   1307\u001b[0m             \u001b[0mbody\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_encode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbody\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'body'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1308\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mendheaders\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbody\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mencode_chunked\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mencode_chunked\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1309\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/http/client.py\u001b[0m in \u001b[0;36mendheaders\u001b[0;34m(self, message_body, encode_chunked)\u001b[0m\n\u001b[1;32m   1256\u001b[0m             \u001b[0;32mraise\u001b[0m \u001b[0mCannotSendHeader\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1257\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_send_output\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmessage_body\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mencode_chunked\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mencode_chunked\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1258\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/http/client.py\u001b[0m in \u001b[0;36m_send_output\u001b[0;34m(self, message_body, encode_chunked)\u001b[0m\n\u001b[1;32m   1035\u001b[0m         \u001b[0;32mdel\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_buffer\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1036\u001b[0;31m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmsg\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1037\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/http/client.py\u001b[0m in \u001b[0;36msend\u001b[0;34m(self, data)\u001b[0m\n\u001b[1;32m    973\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mauto_open\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 974\u001b[0;31m                 \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconnect\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    975\u001b[0m             \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/http/client.py\u001b[0m in \u001b[0;36mconnect\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m    945\u001b[0m         self.sock = self._create_connection(\n\u001b[0;32m--> 946\u001b[0;31m             (self.host,self.port), self.timeout, self.source_address)\n\u001b[0m\u001b[1;32m    947\u001b[0m         \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msock\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msetsockopt\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msocket\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mIPPROTO_TCP\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msocket\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mTCP_NODELAY\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/socket.py\u001b[0m in \u001b[0;36mcreate_connection\u001b[0;34m(address, timeout, source_address)\u001b[0m\n\u001b[1;32m    703\u001b[0m     \u001b[0merr\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 704\u001b[0;31m     \u001b[0;32mfor\u001b[0m \u001b[0mres\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mgetaddrinfo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mhost\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mport\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mSOCK_STREAM\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    705\u001b[0m         \u001b[0maf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msocktype\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mproto\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcanonname\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msa\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mres\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/socket.py\u001b[0m in \u001b[0;36mgetaddrinfo\u001b[0;34m(host, port, family, type, proto, flags)\u001b[0m\n\u001b[1;32m    744\u001b[0m     \u001b[0maddrlist\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 745\u001b[0;31m     \u001b[0;32mfor\u001b[0m \u001b[0mres\u001b[0m \u001b[0;32min\u001b[0m \u001b[0m_socket\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mgetaddrinfo\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mhost\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mport\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfamily\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtype\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mproto\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mflags\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    746\u001b[0m         \u001b[0maf\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msocktype\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mproto\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcanonname\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msa\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mres\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mgaierror\u001b[0m: [Errno -2] Name or service not known",
      "\nDuring handling of the above exception, another exception occurred:\n",
      "\u001b[0;31mURLError\u001b[0m                                  Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-24-3146aca43d3e>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     36\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     37\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 38\u001b[0;31m \u001b[0mgeoGrab\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'l VA Center'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m'Augusta, ME'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-24-3146aca43d3e>\u001b[0m in \u001b[0;36mgeoGrab\u001b[0;34m(stAddress, city)\u001b[0m\n\u001b[1;32m     12\u001b[0m     \u001b[0myahooApi\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mapiStem\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0murl_params\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m     \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0myahooApi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m     \u001b[0mc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0murllib\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrequest\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0murlopen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0myahooApi\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     15\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0mjson\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mloads\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mread\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/urllib/request.py\u001b[0m in \u001b[0;36murlopen\u001b[0;34m(url, data, timeout, cafile, capath, cadefault, context)\u001b[0m\n\u001b[1;32m    221\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    222\u001b[0m         \u001b[0mopener\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_opener\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 223\u001b[0;31m     \u001b[0;32mreturn\u001b[0m \u001b[0mopener\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mopen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0murl\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdata\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mtimeout\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    224\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    225\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0minstall_opener\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mopener\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/urllib/request.py\u001b[0m in \u001b[0;36mopen\u001b[0;34m(self, fullurl, data, timeout)\u001b[0m\n\u001b[1;32m    524\u001b[0m             \u001b[0mreq\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mmeth\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mreq\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    525\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 526\u001b[0;31m         \u001b[0mresponse\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_open\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mreq\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdata\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    527\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    528\u001b[0m         \u001b[0;31m# post-process response\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/urllib/request.py\u001b[0m in \u001b[0;36m_open\u001b[0;34m(self, req, data)\u001b[0m\n\u001b[1;32m    542\u001b[0m         \u001b[0mprotocol\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mreq\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mtype\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    543\u001b[0m         result = self._call_chain(self.handle_open, protocol, protocol +\n\u001b[0;32m--> 544\u001b[0;31m                                   '_open', req)\n\u001b[0m\u001b[1;32m    545\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    546\u001b[0m             \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/urllib/request.py\u001b[0m in \u001b[0;36m_call_chain\u001b[0;34m(self, chain, kind, meth_name, *args)\u001b[0m\n\u001b[1;32m    502\u001b[0m         \u001b[0;32mfor\u001b[0m \u001b[0mhandler\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mhandlers\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    503\u001b[0m             \u001b[0mfunc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mgetattr\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mhandler\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmeth_name\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 504\u001b[0;31m             \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mfunc\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    505\u001b[0m             \u001b[0;32mif\u001b[0m \u001b[0mresult\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    506\u001b[0m                 \u001b[0;32mreturn\u001b[0m \u001b[0mresult\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/urllib/request.py\u001b[0m in \u001b[0;36mhttp_open\u001b[0;34m(self, req)\u001b[0m\n\u001b[1;32m   1344\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1345\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0mhttp_open\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mreq\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1346\u001b[0;31m         \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdo_open\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mhttp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclient\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mHTTPConnection\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mreq\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1347\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1348\u001b[0m     \u001b[0mhttp_request\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mAbstractHTTPHandler\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mdo_request_\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/anaconda3/envs/simple/lib/python3.6/urllib/request.py\u001b[0m in \u001b[0;36mdo_open\u001b[0;34m(self, http_class, req, **http_conn_args)\u001b[0m\n\u001b[1;32m   1318\u001b[0m                           encode_chunked=req.has_header('Transfer-encoding'))\n\u001b[1;32m   1319\u001b[0m             \u001b[0;32mexcept\u001b[0m \u001b[0mOSError\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0merr\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;31m# timeout error\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1320\u001b[0;31m                 \u001b[0;32mraise\u001b[0m \u001b[0mURLError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0merr\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m   1321\u001b[0m             \u001b[0mr\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mh\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mgetresponse\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m   1322\u001b[0m         \u001b[0;32mexcept\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mURLError\u001b[0m: <urlopen error [Errno -2] Name or service not known>"
     ]
    }
   ],
   "source": [
    "import urllib\n",
    "import json\n",
    "\n",
    "\n",
    "def geoGrab(stAddress, city):\n",
    "    apiStem = 'http://where.yahooapis.com/geocode?'\n",
    "    params = {}\n",
    "    params['flags'] = 'J'\n",
    "    params['appid'] = 'aaa0VN6k'\n",
    "    params['location'] = '%s %s' % (stAddress, city)\n",
    "    url_params = urllib.parse.urlencode(params)\n",
    "    yahooApi = apiStem + url_params\n",
    "    print(yahooApi)\n",
    "    c = urllib.request.urlopen(yahooApi)\n",
    "    return json.loads(c.read())\n",
    "\n",
    "\n",
    "from time import sleep\n",
    "\n",
    "\n",
    "def massPlaceFind(fileName):\n",
    "    fw = open('places.txt', 'w')\n",
    "    for line in open(fileName).readlines():\n",
    "        line = line.strip()\n",
    "        lineArr = line.split('\\t')\n",
    "        retDict = geoGrab(lineArr[1], lineArr[2])\n",
    "        if retDict['ResultSet']['Error'] == 0:\n",
    "            lat = float(retDict['ResultSet']['Results'][0]['latitude'])\n",
    "            lng = float(retDict['ResultSet']['Results'][0]['longitude'])\n",
    "            print(\"%s\\t%f\\t%f\" % (lineArr[0], lat, lng))\n",
    "            fw.write('%s\\t%f\\t%f\\n' % (line, lat, lng))\n",
    "        else:\n",
    "            print(\"error fetching\")\n",
    "        sleep(1)\n",
    "    fw.close()\n",
    "\n",
    "\n",
    "geoGrab('l VA Center', 'Augusta, ME')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
